
#include <iostream>
#include <assert.h>
#include <string>
#include <vector>

using namespace std;

template<class K, class V>
struct AVLTreeNode
{
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
    pair<K, V> _kv;
    int _bf;

    AVLTreeNode(const pair<K, V>& kv)
        :_left(nullptr)
         ,_right(nullptr)
         ,_parent(nullptr)
         ,_kv(kv)
         ,_bf(0)
    {}
};

template<class K, class V>
class AVLTree 
{
    typedef AVLTreeNode<K, V> Node;
public:
    bool insert(const pair<K, V>& kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }

        // 找位
        Node* cur = _root;
        Node* parent = nullptr;

        while (cur)
        {
            if (kv.first > cur->_kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (kv.first < cur->_kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else 
            {
                return false;
            }
        }

        // 连接
        cur = new Node(kv);
        if (parent->_kv.first > kv.first)
        {
            parent->_left = cur;
        }
        else 
        {
            parent->_right = cur;
        }
        cur->_parent = parent;

        // 平衡树，置平衡因子
        while (parent)
        {
            if (parent->_right == cur)
            {
                parent->_bf ++ ;
            }
            else
            {
                parent->_bf -- ;
            }

            if (parent->_bf == 0)
            {
                break;
            }
            else if (abs(parent->_bf) == 1)
            {
                parent = parent->_parent;
                cur = cur->_parent;
            }
            else if (abs(parent->_bf) == 2)
            {
                if (parent->_bf == 2 && cur->_bf == 1)
                {
                    RotateL(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == -1)
                {
                    RotateR(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == 1)
                {
                    RotateLR(parent);
                }
                else if (parent->_bf == 2 && cur->_bf == -1)
                {
                    RotateRL(parent);
                }
                else 
                {
                    assert(false);
                }

                return true;
            }
            else 
            {
                assert(false);
            }
        }

        return true;
    }

    ~AVLTree()
    {
        Destroy(_root);
        _root = nullptr;
    }

    bool AVLTreeTrue()
    {
        return _AVLTreeTrue(_root);
    }

    void InOrder()
    {
        _InOrder(_root);
    }
    
private:

    void _InOrder(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }

        _InOrder(root->_left);
        cout << root->_kv.first << ':' << root->_kv.second << endl;
        _InOrder(root->_right);
    }

    bool _AVLTreeTrue(Node* root)
    {
        if (root == nullptr) return true;

        int leftHeight = Height(root->_left);
        int rightHeight = Height(root->_right);
        int diff = rightHeight - leftHeight;

        if (diff != root->_bf)
        {
            cout << "平衡因子异常！！！" << endl;
            return false;
        }

        return abs(diff) < 2 && _AVLTreeTrue(root->_left) && _AVLTreeTrue(root->_right);
    }

    int Height(Node* root)
    {
        if (root == nullptr) return 0;

        return max(Height(root->_left), Height(root->_right)) + 1;
    }

    void Destroy(Node* root)
    {
        if (root == nullptr) return;

        Destroy(root->_left);
        Destroy(root->_right);
        free(root);
    }

    void RotateL(Node* parent)
    {
        Node* sub = parent->_right;
        Node* subL = sub->_left;

        parent->_right = subL;
        if (subL)
            subL->_parent = parent;

        Node* ppNode = parent->_parent;
        sub->_left = parent;
        parent->_parent = sub;

        if (parent == _root)
        {
            _root = sub;
            sub->_parent = nullptr;
        }
        else 
        {
            if (ppNode->_left == parent)
            {
                ppNode->_left = sub;
            }
            else 
            {
                ppNode->_right = sub;
            }
            sub->_parent = ppNode;
        }

        sub->_bf = parent->_bf = 0;
    }

    void RotateR(Node* parent)
    {
        Node* sub = parent->_left;
        Node* subR = sub->_right;

        parent->_left = subR;
        if (subR)
            subR->_parent = parent;

        Node* ppNode = parent->_parent;
        sub->_right = parent;
        parent->_parent = sub;

        if (parent == _root)
        {
            _root = sub;
            sub->_parent = nullptr;
        }
        else 
        {
            if (ppNode->_left == parent)
            {
                ppNode->_left = sub;
            }
            else 
            {
                ppNode->_right = sub;
            }
            sub->_parent = ppNode;
        }

        sub->_bf = parent->_bf = 0;
    }

    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;

        RotateR(parent->_right);
        RotateL(parent);

        subRL->_bf = 0;
        if (bf == -1)
        {
            parent->_bf = 0;
            subR->_bf = 1;
        }
        else if (bf == 1)
        {
            parent->_bf = -1;
            subR->_bf = 0;
        }
        else if (bf == 0)
        {
            parent->_bf = subR->_bf = 0;
        }
        else 
        {
            assert(false);
        }
    }

    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subLR->_bf;

        RotateL(parent->_left);
        RotateR(parent);

        subLR->_bf = 0;
        if (bf == 1)
        {
            parent->_bf = 0;
            subL->_bf = -1;
        }
        else if (bf == -1)
        {
            parent->_bf = 1;
            subL->_bf = 0;
        }
        else if (bf == 0)
        {
            subL->_bf = parent->_bf = 0;
        }
        else 
        {
            assert(false);
        }
    }

    Node* _root = nullptr;
};


